package com.squirrel.michale;

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/11 4:25 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0871 {

    // 0-1 knapsack problem
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int distance = startFuel;
        int stops = 0;
        int index = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        while (true) {
            while (index < stations.length && stations[index][0] <= distance) {
                heap.offer(stations[index++][1]);
            }
            if (distance >= target) {
                return stops;
            }
            if (heap.isEmpty()) {
                return -1;
            }
            distance += heap.poll();
            stops++;
        }
    }

    public static void main(String[] args) {
        int target = 100;
        int startFuel = 10;
        int[][] stations = new int[][]{{10, 60}, {20, 30}, {30, 30}, {60, 40}};

        LeetCode0871 leetCode0871 = new LeetCode0871();
        System.out.println(leetCode0871.minRefuelStops(target, startFuel, stations));
    }
}
